package P1332;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problema da disciplina de Estrutura de Dados e Complexidade de Algoritmos da
 * Pos Graduacao do Periodo 2011.1
 *
 * @see http://br.spoj.pl/problems/DENGUE/
 * @author Elenilson Vieira - 111100371 - elenilson[at]elenilsonvieira.com
 * @since 20 de junho de 2011
 */
public class Main {

    public static final int MAX_DISTANCE = 100;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String line = null;
        int testNumber = 1;
        StringBuilder result = new StringBuilder();

        while (!(line = reader.readLine().trim()).equals("0")) {
            String data[] = line.split(" ");
            int villagesAmount = Integer.parseInt(data[0]);
            int[][] graph = new int[villagesAmount][villagesAmount];
            int townToPostVaccination = 0;

            init(graph);

            for (int i= 0; i < villagesAmount - 1; i++) {
                line = reader.readLine();
                data = line.split(" ");
                int townX = Integer.parseInt(data[0]);
                int townY = Integer.parseInt(data[1]);

                graph[townX - 1][townY - 1] = 1;
                //graph[townY - 1][townX - 1] = 1;
            }

            print(graph);
            System.out.println("AA>>>>>>>");

            /*** Aplica o algoritmo de floyd ***/
            floyd(graph);

            print(graph);
            System.out.println(">>>>>>>>>");

        /*** Ve quem tem a menor distancia ***/
        int maxDistance = MAX_DISTANCE;
        for (int i= 0; i < villagesAmount; i++) {
            int maxDistanceI = 0;
            for (int j= 0; j < villagesAmount; j++) {
                if(graph[i][j] > maxDistanceI)
                    maxDistanceI = graph[i][j];
            }

            if(maxDistanceI <= maxDistance){
                maxDistance = maxDistanceI;
                townToPostVaccination = i;
            }
        }

            result.append(testNumber == 1 ?
                    String.format("Teste %d\n%d\n", testNumber++, townToPostVaccination + 1) :
                    String.format("\nTeste %d\n%d\n", testNumber++, townToPostVaccination + 1));
        }

        System.out.print(result.toString());
    }

    /**
     * Executa o algoritmo de Floyd-Warshall
     *
     * @param graph o grafo com as distancias entre os nos (0 pra diagonal
     * principal e MAX_VALUE pra nos nao ligados diretamente)
     */
    private static void floyd(int graph[][]){
        for(int i = 0; i < graph.length; i++)
            for(int j = 0; j < graph.length; j++)
                for(int k = 0; k < graph.length; k++)
                    graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
    }

    /**
     * Retorna o menor valor entre os dois passados como argumento
     *
     * @param i o primeiro valor
     * @param j o segundo valor
     *
     * @return o menor valor entre i e j
     */
    private static int min(int i, int j) {
        return i < j ? i : j;
    }

    /**
     * Imprime o grafo
     *
     * @param graph o grafo a ser impresso
     */
    private static void print(int[][] graph) {
        for (int i= 0; i < graph.length; i++) {
            for (int j= 0; j < graph[i].length; j++) {
                System.out.println(String.format("graph[%d][%d] = %d", i, j, graph[i][j]));
            }
        }
    }

    /**
     * Inicia o array com a diagonal principal sendo 0 e os outros valores como MAX_VALUE
     *
     * @param graph o grafo
     */
    private static void init(int[][] graph) {
        for (int i= 0; i < graph.length; i++) {
            for (int j= 0; j < graph[i].length; j++) {
                if(i != j)
                    graph[i][j] = MAX_DISTANCE;
            }
        }
    }

}
